package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * https://leetcode.com/problems/maximal-rectangle/
 * see 221
 *
 * @author tzp
 * @since 2020/9/24
 */
public class LC85 implements DynamicProblem {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) return 0;
        int[][] dp = new int[matrix.length][matrix[0].length];
        //dp[i][j]表示第i行第j个格, 往左有多少个连续1
        int max = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (j == 0) {
                    dp[i][j] = matrix[i][j] == '1' ? 1 : 0;
                } else {
                    if (matrix[i][j] == '1') {
                        dp[i][j] = 1 + dp[i][j - 1];
                    } else {
                        dp[i][j] = 0;
                    }
                }
                int tmpMax = 0;
                if (i == 0) {
                    tmpMax = dp[i][j];
                } else {
                    int width = Integer.MAX_VALUE;
                    for (int k = i; k >= 0; k--) {
                        int height = i - k + 1;
                        width = Math.min(width, dp[k][j]);
                        tmpMax = Math.max(tmpMax, width * height);
                    }
                }
                max = Math.max(max, tmpMax);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        char[][] a = {
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}};
        System.out.println(new LC85().maximalRectangle(a));
    }
}
